/* 求无向图的连通分量个数 */

#include <iostream>
#include "algraph.h"
using namespace std;

// 深度优先搜索
void DFS(ALGraph *G, int v, int visit[])
{
  // 更新访问标记
  visit[v] = 1;
  
  // 找到邻接结点
  ArcNode *p = G->adjlist[v].firstarc;
  
  // 如果邻接结点不为空
  while (p != NULL)
  {
    // 如果邻接结点未被访问
    if (visit[p->adjvex] == 0)
      DFS(G, p->adjvex, visit); // 深度优先
    
    // 到下一个邻接结点
    p = p->nextarc;
  }
}

// 计算无向图的连通分量个数
int func(ALGraph *G)
{
  // 访问标记，初始时均未被访问
  int visit[maxsize];
  for (int i = 0; i < G->numver; ++i)
    visit[i] = 0;
  
  // 记录连通分量个数
  int count = 0;
  
  // 遍历结点
  for (int j = 0; j < G->numver; ++j)
    if (visit[j] == 0) // 如果未被访问
    {
      DFS(G, j, visit); // 深度优先搜索
      count++; // 连通分量个数+1
    }
  
  // 访问连通分量个数
  return count;
}

int main()
{
  // 创建图 -- 邻接表
  ALGraph *G = create_algraph(4, 3);
  cout << "无向图的连通分量个数为：" << func(G);
  return 0;
}